package 堆;

import 动态数组.ClassArray;

public class MaxHeap<E extends Comparable<E>>  {
    private ClassArray<E> data;

    public MaxHeap(int cap) {
        this.data = new ClassArray<>(cap);
    }

    private int parent(int index){
        return (index - 1) / 2;
    }
    private int leftChild(int index){
        return 2 * index + 1;
    }
    private int rightChild(int index){
        return 2 * index + 2;
    }
    /*入堆*/
    public void add(E e){
        data.addLast(e);
        shiftUp(data.getSize() - 1);
    }

    /*从下到上调整*/
    private void shiftUp(int index) {
        while (index > 0 && data.get(index).compareTo(data.get(parent(index))) > 0){
            data.swap(index, parent(index));
            index = parent(index);
        }
    }
    /*出堆*/
    public E deleteMax() {
      E res = data.get(0);
      data.swap(data.getSize() - 1, 0);
      data.deleteLast();
      shiftDown(0);
      return res;
    }

    /*从上到下调整*/
    private void shiftDown(int index) {
        while (leftChild(index) < data.getSize()){
            int j = leftChild(index);
            if((j+1) < data.getSize() &&
            data.get(j+1).compareTo(data.get(j)) > 0){
                j = rightChild(index);
            }
            if (data.get(index).compareTo(data.get(j)) > 0){
                break;
            }
            data.swap(j, index);
            index = j;
        }
    }
    /*replace, 取出最大元素，放入新元素*/
    public E replace(E e){
        E res = deleteMax();
        add(e);
        return res;
    }
    /*heapify, 将数组调整为堆*/
    public void MaxHeap(E[]arr){
        this.data = new ClassArray<>(arr);
        for(int i = parent(arr.length - 1); i>= 0; i--){
            shiftDown(i);
        }
    }
    public int getSize(){
        return data.getSize();
    }
    public boolean isEmpty(){
        return data.isEmpty();
    }
    public E getMax(){
        return data.get(0);
    }

    


}
